﻿#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
//int main()
//{
//	string s1, s2;
//	
//	while (cin >> s1 >> s2)
//	{
//		int hash[26] = { 0 };
//		for (auto c1 : s1)
//		{
//			hash[c1 - 'A']++;
//		}
//		int flag = 1;
//		for (auto c2 : s2)
//		{
//			hash[c2 - 'A']--;
//			if (hash[c2 - 'A'] < 0)
//			{
//				flag = 0;
//			}
//		}
//
//		if (flag)
//		{
//			cout << "Yes" << endl;
//		}
//		else
//		{
//			cout << "No" << endl;
//		}
//	}
//	return 0;
//}


//int main()
//{
//	int n;
//	cin >> n;
//	vector<int> a(3 * n);
//	for (int i = 0; i < 3 * n; i++)
//	{
//		cin >> a[i];
//	}
//	sort(a.begin(), a.end());
//	int cur = 3 * n - 2;
//	int count = 0;
//	int sum = 0;
//	while (count < n)
//	{
//		sum += a[cur];
//		cur -= 2;
//		count++;
//	}
//	cout << sum << endl;
//	return 0;
//}



//int main()
//{
//    long long int x;
//    cin >> x;
//    long long int a = sqrt(x);
//    long long int y1, y2;
//    y1 = a * a;
//    y2 = (a + 1) * (a + 1);
//    if (abs(x - y1) < abs(x - y2))
//    {
//        cout << y1 << endl;
//    }
//    else
//    {
//        cout << y2 << endl;
//    }
//
//    return 0;
//}



//int n, m;
//map<int, int> Hash;
//
//bool check(int x) // 判断最多⼈数为 x 时，能否分成 m 组
//{
//    int g = 0; // 能分成多少组
//    for (auto& [a, b] : Hash)
//    {
//        g += b / x + (b % x == 0 ? 0 : 1);
//    }
//    return g <= m;
//}
//int main()
//{
//    cin >> n >> m;
//    int Max = 0;
//
//    for (int i = 0; i < n; i++)
//    {
//        int x = 0;
//        cin >> x;
//        Hash[x]++;
//        Max = max(Max, Hash[x]);
//    }
//
//    int z = Hash.size();
//    if (z > m)
//    {
//        cout << -1 << endl;
//    }
//    else
//    {
//        for (int i = 1; i <= Max; i++)
//        {
//            if (check(i))
//            {
//                cout << i << endl;
//                break;
//            }
//        }
//    }
//    return 0;
//}


//class StringFormat
//{
//public:
//    string formatString(string A, int n, vector<char> arg, int m)
//    {
//        string B;
//        int k = 0;
//        for (int i = 0; i < n; i++)
//        {
//            if (A[i] == '%' && A[i + 1] == 's')
//            {
//
//                B += arg[k++];
//                i++;
//            }
//            else
//            {
//                B += A[i];
//            }
//        }
//        while (k < m)
//        {
//            B += arg[k++];
//        }
//        return B;
//    }
//};




//bool isprime(int x)
//{
//	if (x < 2)
//	{
//		return false;
//	}
//	for (int i = 2; i <= sqrt(x); i++)
//	{
//		if (x % i == 0)
//		{
//			return false;
//		}
//	}
//	return true;
//}
//int main()
//{
//	int a, b;
//	cin >> a >> b;
//	int count = 0;
//	int flag = 0;
//	for (int i = max(a, 10); i <= b; i++)
//	{
//		int j = i;
//		vector<int> arr;
//		while (j)
//		{
//			arr.push_back(j % 10);
//			j /= 10;
//		}
//		int n = arr.size();
//		flag = 0;
//		for (int j = 0; j < n; j++)
//		{
//			for (int k = 0; k < n; k++)
//			{
//				if (arr[j] != 0 && j != k)
//				{
//					int tmp = arr[j] * 10 + arr[k];
//					if (isprime(tmp))
//					{
//						flag = 1;
//						break;
//					}
//				}
//			}
//			if (flag)
//			{
//				count++;
//				break;
//			}
//		}
//	}
//	cout << count << endl;
//	return 0;
//}



//int main()
//{
//    string s;
//    cin >> s;
//    int m;
//    cin >> m;
//    int n = s.size();
//    int left = 0, right = 4;
//    int count = 0, Max = 0;
//    for (int i = 0; i < n; i++)
//    {
//        count = 0;
//        for (int j = i; j < i + m; j++)
//        {
//            if (s[j] == 'C' || s[j] == 'G')
//            {
//                count++;
//            }
//        }
//        if (count > Max)
//        {
//            Max = count;
//            left = i;
//            right = i + m - 1;
//        }
//    }
//    cout << s.substr(left, m);
//    return 0;
//}


//int main()
//{
//    long long int n;
//    cin >> n;
//    long long int t = 0;
//    vector<int> a;
//    while (n)
//    {
//        int m = n % 10;
//        if (m % 2)
//        {
//            a.push_back(1);
//        }
//        else
//        {
//            a.push_back(0);
//            t++;
//        }
//        n /= 10;
//    }
//    if (t == a.size())
//    {
//        cout << 0;
//    }
//    else
//    {
//        int flag = 1;
//        for (auto rit = a.rbegin(); rit != a.rend(); ++rit)
//        {
//            if (*rit == 0 && flag)
//            {
//                continue;
//            }
//            if (*rit != 0)
//            {
//                flag = 0;
//            }
//            cout << *rit;
//        }
//    }
//    return 0;
//}


//int main()
//{
//    int n, k;
//    cin >> n >> k;
//    vector<long long int> a(n + 1);
//    vector<long long int> b(n + 1);
//    vector<long long int> a1(n + 1);
//    vector<long long int> b1(n + 1);
//    int ret = 0;
//    long long int Max = 0;
//
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> a[i];
//
//    }
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> b[i];
//    }
//    for (int i = 1; i <= n; i++)
//    {
//        a1[i] = a1[i - 1] + a[i];
//        b1[i] = b1[i - 1] + b[i];
//        if (i >= k)
//        {
//            a1[i] -= a[i - k];
//            b1[i] -= b[i - k];
//        }
//        if (a1[i] > Max)
//        {
//            Max = a1[i];
//            ret = i;
//        }
//    }
//    for (int i = 1; i <= n; i++)
//    {
//        if (a1[i] == Max && ret != i)
//        {
//            if (b1[i] < b1[ret])
//            {
//                ret = i;
//            }
//        }
//    }
//    cout << ret;
//    return 0;
//}



//int main()
//{
//    int n, k;
//    cin >> n >> k;
//    vector<long long int> a(n + 1);
//    vector<long long int> b(n + 1);
//    vector<long long int> a1(n + 1);
//    vector<long long int> b1(n + 1);
//    int ret = 0;
//    long long int Max = 0;
//
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> a[i];
//
//    }
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> b[i];
//    }
//    for (int i = 1; i <= n; i++)
//    {
//        int j = i;
//        while (j < i + k && j <= n)
//        {
//            a1[i] += a[j];
//            b1[i] += b[j];
//            j++;
//        }
//        if (a1[i] > Max)
//        {
//            Max = a1[i];
//            ret = i;
//        }
//    }
//    for (int i = 1; i <= n; i++)
//    {
//        if (a1[i] == Max && ret != i)
//        {
//            if (b1[i] < b1[ret])
//            {
//                ret = i;
//            }
//
//        }
//    }
//    cout << ret;
//    return 0;
//}




//class Solution
//{
//public:
//    string compressString(string param)
//    {
//        int count = 1;
//        int n = param.size();
//        string ret;
//        int i = 0;
//        while (i < n)
//        {
//            ret += param[i];
//            int j = i;
//            while (j < n - 1 && param[j] == param[j + 1])
//            {
//                j++;
//                count++;
//            }
//            if (count != 1)
//            {
//                ret += to_string(count);
//            }
//            count = 1;
//            i = j + 1;
//        }
//        return ret;
//    }
//};





//int main()
//{
//    int n, k;
//    cin >> n >> k;
//    vector<int> a(n);
//    vector<int> b(n);
//
//    for (int i = 0; i < n; i++)
//    {
//        cin >> a[i];
//    }
//    for (int i = 0; i < n; i++)
//    {
//        cin >> b[i];
//    }
//    vector<pair<int, int>> m(n);
//    for (int i = 0; i < n; i++)
//    {
//        m[i] = { b[i],a[i] };
//    }
//
//    sort(m.begin(), m.end(), [](const pair<int, int>& a, const pair<int, int>& b)
//        {
//            if (a.first == b.first)
//            {
//                return a.second < b.second;
//            }
//            return a.first > b.first;
//        });
//    long long s = 0, t = 0;
//    int count = 0;
//    for (const auto& e : m)
//    {
//
//        s += e.second;
//        t += e.first;
//        count++;
//        if (count == k)
//        {
//            break;
//        }
//    }
//    cout << s << " " << t << endl;
//
//    return 0;
//}


class Solution
{
    int dp[1010] = { 0 };
public:
    int knapsack(int V, int n, vector<vector<int> >& vw)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = V; j >= vw[i][0]; j--)
            {
                dp[j] = max(dp[j], dp[j - vw[i][0]] + vw[i][1]);
            }
        }
        return dp[V];
    }
};